In a cluster-based routing protocol, network nodes are organized into clusters, or administrative groups, to simplify the dissemination of routing information in the network and improve the scalability of the routing protocol. Traditionally, the grouping of nodes into clusters is based on a configured cluster identifier. Existing link-state routing protocols such as PNNI (Private Network-to-Network Interface) and OSPF (Open Shortest Path First) are based on this concept. PNNI is a hierarchical, dynamic link-state routing protocol defined by the ATM Forum for use in ATM networks (“Private Network-to-Network Interface Specification Version 1.0 (PNNI 1.0)”, ATM Forum af-pnni-0055.000, March 1996). Here, nodes are organized in clusters known as “peer groups” based on a cluster identifier, or “peer group id”, which is configured on a per-node and per-hierarchy level basis. The OSPF routing protocol is widely used in IP (Internet Protocol) networks for routing of IP data (J. Moy, “OSPF v2.0”, Internet Standard, STD 0054, April 1998). Here, the nodes in a cluster interface with a common OSPF area and the cluster identifier is an area id which is configured per-OSPF interface.
In general in such routing protocols, when a physical node is activated it starts sending Hello messages to discover the identity of its neighbors. The hello message includes the cluster id of the sending node so that a receiving node can determine whether the sending node belongs to the same cluster as itself (the cluster id's match) or not (the cluster id's are different). When the cluster id's match, the receiving node can transmit the necessary routing information to establish an adjacency at the routing protocol level between the two nodes, whereby the newly activated node effectively joins the cluster of the sending node. The routing information transmitted here typically comprises the contents of the sending node's routing database so that the routing databases of the two nodes are synchronized.
Clustering is used to improve the scalability of a routing protocol in that, in operation, the routing information exchanged by nodes which are members of the same cluster is always richer in detail than the information exchanged by nodes belonging to different clusters. For example, in PNNI the details of each peer group are abstracted into a single logical node (a “logical group node” or LGN) which is all that can be seen by nodes outside of that peer group. The details of nodes and links in a peer group are known only to nodes in that peer group. A network without clusters, or with one single cluster, is known as a flat network. In a flat network, every node knows everything about every other node. Any implementation of a cluster-based routing protocol has a finite maximum cluster size which restricts the number of nodes which can be supported in the same cluster. Above this maximum number the routing protocol is generally either in permanent overload state or collapses.
Traditionally when designing a network, a clustering plan is elaborated. The clustering plan defines the number of clusters with the relevant cluster identifiers, and assigns every node (or routing protocol interface of a node as appropriate) to a cluster. Network clustering plans are generally based on factors such as topological criteria (e.g. nodes in the same building belong to the same cluster), addressing criteria (e.g. to maximize address summarization), organizational criteria (e.g. office branches or network backbone), capacity of links, etc. Thus the cluster id is used to group nodes through administrative means and to force a clustering structure in a network.
In a mobile networking environment, this clustering mechanism has been fully exploited with the mobility of ATM networks specified by the ATM forum in the PNNI mobility extensions (“PNNI Addendum for Mobility Extensions v1.0”, ATM Forum af-ra-0123.000, April 1999). Here, a logical group node abstracting a mobile ATM network can roam in the PNNI hierarchy of a terrestrial backbone network. Access point nodes (to which mobile networks can connect) in the backbone network are configured to belong to different clusters (i.e. they have different peer group id's). A mobile logical group node, when joining the hierarchy of the backbone network, dynamically adopts the cluster id of one of its current access points. This concept has proved successful because it allows administrative enforcement of a clustering structure around the mobile networks attached to an access point. A master-slave relationship is defined between an access point node and the mobile networks attached to it. Logically, it is always the logical group node representing a mobile network that adapts its cluster id to that of the access point and not vice versa.
Clustering through administrative means is not, however, appropriate in the case of ad hoc networks. An ad hoc network is a network built dynamically by a number of nodes which connect together in a non-deterministic manner, for example nodes in different mobile networks which establish a connection as a result of common geographical location. Ad hoc networks are characterized by the connectivity changing between nodes and the unpredictability of who will be connected to whom and when. A node, for instance, might move out of reach of its current ad hoc network (leave the ad hoc network), and might establish connectivity with a new ad hoc network (join the ad hoc network). In such an ad hoc environment, use of a cluster-based routing protocol as discussed above would imply manual reconfiguration of the clusters (i.e. the cluster id's) as connectivity changes. A master-slave system, as in the PNNI mobility extensions, cannot help since in general no mobile node can be assumed to be fixed within an ad hoc network and thus be the master and owner of the cluster id. Instead of a master-slave type relationship between nodes, there is a peer-to-peer type relationship where all mobile nodes are “equal”. Thus, in an ad hoc environment, the natural way to cluster nodes is through their connectivity, each “island” of nodes (i.e. nodes with connectivity between themselves but no connectivity outside the island) building its own cluster. A problem with this approach, however, is that situations can be envisaged where all mobile nodes are connected, directly or indirectly, to all other mobile nodes. This would result in one huge cluster (equivalent to a flat network or no clustering), prejudicing efficient operation of the routing protocol and potentially causing routing protocol collapse. A mobile node might also, due to its motion, become a “communication bridge” between two previously disconnected ad hoc networks, the resulting situation similarly prejudicing integrity of the routing protocol. Accordingly, it would be desirable to provide a method for controlling the clustering of nodes which operates effectively in an ad hoc environment.